package com.arithmetic.search;

/**
 * 查找
 *
 * @author chenyichang
 * @since 2022/8/17
 */
public class SearchArithmetic {


    /**
     * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * [
     * [1,2,8,9],
     * [2,4,9,12],
     * [4,7,10,13],
     * [6,8,11,15]
     * ]
     * 给定 target = 7，返回 true。
     * <p>
     * 给定 target = 3，返回 false。
     */
    public static boolean Find(int target, int[][] array) {
        if (array.length == 0 || array[0].length == 0) {
            return false;
        }
        //矩阵走法（只能从左下角、或者右上角 进行遍历）
        //从左下角开始走（元素大就往上走，元素小了就往右走）

        int i = 0;//行
        int j = array.length - 1;//列
        while (i < array.length && j >= 0) {
            if (array[j][i] == target) {
                return true;
            }
            if (array[j][i] > target) {
                //元素大 走上
                j--;
            } else {
                //元素小 走右
                i++;
            }

        }
        return false;
    }

    /**
     * 二分查找
     * 无重复数字的升序数组的二分查找
     * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
     * 例如：[-1,0,3,4,6,10,13,14],13
     * 返回 6（13在数组中出现的下标为6）
     *
     * @param nums   给定数组
     * @param target 查找值
     * @return 返回target所在的下标，如果不存在则返回-1
     */
    public static int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                return middle;
            }
            if (nums[middle] > target) {
                //往左边找
                right = middle - 1;
            } else {
                //往右边找
                left = middle + 1;
            }
        }
        return -1;
    }
}


